﻿#include <iostream>

#define MAX(a,b) (a>b?a:b)

/**
 * 暴力尝试, 子尝试需要传入去掉arr[index]之后的新数组
 */
static int tryBurst(int* arr, const size_t arrSize, const int index)
{
	if (arrSize == 1)
	{
		return arr[0];
	}

	int cur = arr[index];
	int curScore;
	int leftScore = 0;
	int tmpScore;
	int* leftArr = (int*)malloc((arrSize - 1) * sizeof(int));

	if (index == 0)
	{
		curScore = cur * arr[1];
		memcpy_s(leftArr, (arrSize - 1) * sizeof(int), arr + 1, (arrSize - 1) * sizeof(int));
	}
	else if (index == arrSize - 1)
	{
		curScore = cur * arr[arrSize - 2];
		memcpy_s(leftArr, (arrSize - 1) * sizeof(int), arr, (arrSize - 1) * sizeof(int));
	}
	else
	{
		curScore = cur * arr[index - 1] * arr[index + 1];
		int leftIndex = 0;
		for (int i = 0; i < arrSize; i++)
		{
			if (i == index) continue;

			leftArr[leftIndex++] = arr[i];
		}
	}

	for (int i = 0; i < (arrSize - 1); i++)
	{
		tmpScore = tryBurst(leftArr, arrSize - 1, i);
		leftScore = MAX(leftScore, tmpScore);
	}

	int total = curScore + leftScore;
	free(leftArr);
	return total;
}

#define INVALID_SCORE 0x81ffffff

/**
 * 暴力递归，从l到r，尝试每个气球最后被打爆
 */
static int lastBurst(const int* arr, const size_t arrSize, int l, int r)
{
	if (l > r || l < 0 || r >= arrSize) return INVALID_SCORE;

	if (l == r)
	{
		return arr[l - 1] * arr[l] * arr[l + 1];
	}

	int cur;
	int max = 0;
	for (int i = l; i <= r; i++)
	{
		if (i == l)
		{
			cur = lastBurst(arr, arrSize, l + 1, r) + arr[l - 1] * arr[l] * arr[r + 1];
		}
		else if (i == r)
		{
			cur = lastBurst(arr, arrSize, l, r - 1) + arr[l - 1] * arr[r] * arr[r + 1];
		}
		else
		{
			cur = lastBurst(arr, arrSize, l, i - 1) + lastBurst(arr, arrSize, i + 1, r) + arr[l - 1] * arr[i] * arr[r + 1];
		}

		max = MAX(max, cur);
	}

	return max;
}

/**
 * 动态规划
 */
static int lastBurstDp(const int* arr, const size_t arrSize)
{
	int* dp = (int*)malloc(arrSize * arrSize * sizeof(int));
	memset(dp, 0, arrSize * arrSize * sizeof(int));

	// (l,l)
	for (int l = 1; l < arrSize - 1; l++)
	{
		dp[l + l * arrSize] = arr[l - 1] * arr[l] * arr[l + 1];
	}

	int cur;
	int max;
	int r;
	for (int added = 1; added < arrSize - 2; added++)
	{
		for (int l = 1; l < arrSize - 1; l++)
		{
			//dp[l + (l + added) * arrSize] =
			r = l + added;
			if (r >= arrSize - 1) continue;

			max = 0;
			for (int i = l; i <= r; i++)
			{
				if (i == l)
				{
					cur = dp[l + 1 + r * arrSize] + arr[l - 1] * arr[l] * arr[r + 1];
				}
				else if (i == r)
				{
					cur = dp[l + (r - 1) * arrSize] + arr[l - 1] * arr[r] * arr[r + 1];
				}
				else
				{
					cur = dp[l + (i - 1) * arrSize] + dp[i + 1 + r * arrSize] + arr[l - 1] * arr[i] * arr[r + 1];
				}

				max = MAX(max, cur);
			}

			dp[l + r * arrSize] = max;
		}
	}

	int res = dp[1 + (arrSize - 2) * arrSize];
	free(dp);
	return res;
}

/**
 * 给定一个数组arr，代表一排有分数的气球。每打爆一个气球都能获得分数，假设打爆气球的分数为X，获得分数的规则如下：
 * 1) 如果被打爆气球的左边有被打爆的气球，找到离被打爆气球最近的气球，假设分数是L；如果被打爆气球的右边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数是R。获得分数是L*X*R.
 * 2) 如果被打爆气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数是L；如果被打爆气球的右边所有气球都已经被打爆, 获得分数是L*X.
 * 3) 如果被打爆气球的左边所有的气球都已经被打爆；如果被打爆气球的右边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数是R；如果被打爆气球的右边所有气球都已经被打爆，获得分数是X*R.
 * 4) 如果被打爆气球的左边和右边所有的气球都已经被打爆，获得分数是X。
 * 
 * 目标是打爆所有气球，获得每次打爆的分数。通过选择打爆气球的顺序，可以得到不同的总分，请返回能获得的最大分数.
 * 
 * 举例:
 * arr=[3,2,5]
 * 如果先打爆3，获得3*2；再打爆2，获得2*5；最后打爆5，获得5；最后总分21.
 * 如果先打爆3，获得3*2；再打爆5，获得2*5；最后打爆2，获得2；最后总分18.
 * 如果先打爆2，获得3*2*5；再打爆3，获得3*5；最后打爆5，获得5；最后总分50.
 * 如果先打爆2，获得3*2*5；再打爆5，获得3*5；最后打爆3，获得3；最后总分48.
 * 如果先打爆5，获得2*5；再打爆3，获得3*2；最后打爆2，获得2；最后总分18.
 * 如果先打爆5，获得2*5；再打爆2，获得3*2；最后打爆3，获得3；最后总分19.
 * 返回能获得的最大分数是50.
 * 
 * 思路：
 * 动态规划，根据最后打爆哪个气球进行尝试。为了方便处理，给arr的最前和最后各追加一个1，两端的1永远不会被打爆。
 * f(L,R), L-1的气球一定没爆，R+1的气球一定没爆，从L到R，尝试每个位置的气球最后打爆。
 * 
 * 举例:
 *        arr:  1   3   2   7   4   6   2   1
 *   position:  0   1   2   3   4   5   6   7
 * 
 * 假设arr[0]和arr[7]一定不会爆，调用f(1,6)
 * 情况1: 位置1最后爆，f(2,6)+arr[0]*arr[1]*arr[7]
 * 情况2: 位置6最后爆, f(1,5)+arr[0]*arr[6]*arr[7]
 * 情况3: 位置2最后爆，f(1,1)+f(3,6)+arr[0]*arr[2]*arr[7]
 * ...
 * 
 * dp表:
 *           1   3   2   7   4   6   2   1
 *           0   1   2   3   4   5   6   7   L
 * -----------------------------------------------
 *    1   0| X   X   X   X   X   X   X   X         
 *    3   1| X   6                       X         
 *    2   2| X      42                   X         
 *    7   3| X          56               X         
 *    4   4| X             168           X         
 *    6   5| X                  48       X         
 *    2   6| X                      12   X         
 *    1   7| X   X   X   X   X   X   X   X         
 *        R|        
 *  
 * 先把L==R的格子填好，填写依据: dp[L,L]=arr[L-1]*arr[L]*arr[L+1].
 * 
 * 对于普遍位置(L,R), 依赖(L+1,R),(L,R-1),(L,L),(L+2,R),(L,L+1),(L+3,R),(L,L+2),(L+4,R),(L,L+3),(L+5,R),...
 * 
 * f(1,2)依赖于f(1,1),f(2,2)
 * f(2,3)依赖于f(2,2),f(3,3)
 * f(1,3)依赖于f(1,1),f(3,3),f(1,2),f(2,3)
 * f(2,4)依赖于f(3,4),f(2,3),f(2,2),f(4,4)
 * 故先搞定f(L,L+1),然后搞定f(L,L+2),然后f(L,L+3)...
 */
int main_burstBalloons()
{
	int arr[] = {7,9,3,5,12,4,8,10,};
	auto arrSize = sizeof(arr) / sizeof(int);

	int maxScore = 0;
	int cur;
	for (int i = 0; i < arrSize; i++)
	{
		cur = tryBurst(arr, arrSize, i);
		maxScore = MAX(cur, maxScore);
	}

	printf("tryBurst: %d\n", maxScore);

	// arr两端各补1
	int* assistantArr = (int*)malloc((arrSize + 2) * sizeof(int));
	memcpy_s(assistantArr + 1, arrSize * sizeof(int), arr, arrSize * sizeof(int));
	assistantArr[0] = 1;
	assistantArr[arrSize + 1] = 1;

	maxScore = lastBurst(assistantArr, arrSize + 2, 1, arrSize);
	printf("lastBurst: %d\n", maxScore);

	maxScore = lastBurstDp(assistantArr, arrSize + 2);
	printf("dp: %d\n", maxScore);
	free(assistantArr);
	return 0;
}